package leetcode.字符串;

/**
 * 最长公共前缀
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1:
 *
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 *
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 *
 *
 *
 */
public class Test14最长公共前缀 {

    /**
     * 问题求的是：公共【前缀】
     * 所以只需要比对各个字符串的前缀即可。
     *
     * 比对方法也很简单：从第1个字符串开始遍历，
     * 检查每个字符串的每一个字符是否和第0个字符串的相应位置
     * 的字符相等，是的就记录有几个相同的
     *
     * 那么遍历第2个第3个字符串的时候，也会记录一个公共前缀的长度
     * 最后返回的是整个过程里面最短的即可
     *
     * @param strs 字符串数组
     * @return 公共的前缀
     */
    public static String longestCommonPrefix(String[] strs) {
        int len = 0;
        if (strs.length == 0 || strs[0].equals("") || strs[0] == null) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        boolean continueProgream = true;
        for (int k = 1; k < strs.length; k++) {
            if (continueProgream == false) {
                break;
            }
            // 记录本次比较的公共字符相同个数
            int l = 0;
            // 比较当前字符串的各个字符是否与另外的字符串的各个字符相同
            for (int i = 0; i < strs[0].length(); i++) {
                try {
                    if (strs[0].charAt(i) == strs[k].charAt(i)) {
                        l++;
                    } else {
                        // 如果从下标为0开始两个字符就是不一样的话，则结束程序
                        if (i == 0) {
                            continueProgream = false;
                        }
                        break;
                    }
                    // 首次比较要给len赋初值
                    if (k == 1) {
                        len = l;
                    }
                } catch (Exception e) {
                    break;
                }
            }
            // 每比较一个字符串后要取最小的len
            if (l < len) {
                len = l;
            }
        }
        return strs[0].substring(0, len);
    }

    public static void main(String[] args) {
        String[] s = new String[]{"aac","a","accc"};
        System.out.println(longestCommonPrefix(s));
    }
}
